package gold.contest;

import gold.utils.InputUtil;

import java.util.*;
import java.util.stream.Collectors;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC6122 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int minOperations(int[] nums, int[] numsDivide) {
            int greatestCommonFactor = 0;
            for (int num : numsDivide) {
                greatestCommonFactor = gcd(greatestCommonFactor, num);
            }

            TreeMap<Integer, Integer> cntMap = new TreeMap<>();
            for (int num : nums) {
                cntMap.put(num, cntMap.getOrDefault(num, 0) + 1);
            }

            int deleteCnt = 0;
            for (Integer num : cntMap.keySet()) {
                if (greatestCommonFactor % num == 0) return deleteCnt;
                deleteCnt += cntMap.get(num);
            }

            return -1;
        }

        int gcd(int a, int b) {
            return a == 0 ? b : gcd(b % a, a);
        }


    }


    class Solution_Time_Exceed {
        public int minOperations(int[] nums, int[] numsDivide) {
            final CommonMultiple commonMultiple = new CommonMultiple();
            int greatestCommonFactor = commonMultiple.getCommonMultiple(numsDivide); // greatest common factor  greatestCommonFactor
//            TreeSet<Integer> divisors = new TreeSet<>(commonMultiple.getDivisors(greatestCommonFactor));
//            extendDivisors(divisors, greatestCommonFactor); // 无必要步骤

            TreeMap<Integer, Integer> cntMap = new TreeMap<>();
            for (int num : nums) {
                cntMap.put(num, cntMap.getOrDefault(num, 0) + 1);
            }

            int deleteCnt = 0;
            for (Integer num : cntMap.keySet()) {
                if (greatestCommonFactor % num == 0) return deleteCnt;
                deleteCnt += cntMap.get(num);
            }

            return -1;
        }

        public void extendDivisors(TreeSet<Integer> divisors, int limit) {
            if (limit == 1) return;
            final List<Integer> divisorList = divisors.stream().collect(Collectors.toList());
            for (Integer div : divisorList) {
                int curNum = limit;
                while (curNum % div == 0) {
                    divisors.add(curNum / div);
                    curNum /= div;
                }
            }

            divisors.add(limit);
        }

        public class CommonMultiple {

            /**
             * 得到最大公因数的方法
             *
             * @param data1 传入数组
             * @return 返回最大公倍数
             */
            private int getCommonMultiple(int[] data1) {
                List<List<Integer>> divisorList = new ArrayList<>();
                for (int data : data1) {
                    divisorList.add(getDivisors(data));
                }
                return getResult(divisorList);
            }

            /**
             * 得到一个数的全部素数因子
             *
             * @param data 传入一个整数
             * @return 返回素数因子
             */
            private List<Integer> getDivisors(int data) {
                List<Integer> primeList = new ArrayList<>();
                int k = Math.abs(data);
                int sum = 1;
                if (!isPrime(data)) { //如果这个数是素数的话，直接返回
                    int len = (int) Math.sqrt(Math.abs(data));
                    for (int i = 2; i <= len; i++) { //任何一个数都可以分解为素数因子的乘积
                        if (isPrime(i)) {
                            while (data % i == 0) {
                                sum *= i;
                                if (sum <= k) {
                                    primeList.add(i);
                                }
                                data = data / i;
                                if (isPrime(data)) {
                                    primeList.add(data);
                                    sum *= data;
                                    break;
                                }
                            }
                            if (sum == k)
                                break;
                        }
                    }
                } else {
                    primeList.add(data);
                }
                return primeList;
            }

            private boolean isPrime(int data) {
                for (int i = 2; i <= Math.sqrt(Math.abs(data)); i++) {
                    if (data % i == 0)
                        return false;
                }
                return true;
            }

            /**
             * 通过将各个数的素数因子传入该方法，得到最大公因数
             * 实际就是求一组数的交集
             * 如果这组数存在最大公因数，则最大公因数必定在素数因子最小的集合里
             *
             * @param divisorList
             * @return
             */
            private int getResult(List<List<Integer>> divisorList) {
                int result = 1;   //存储最终结果，如果返回是1的话，则说明不存在最大公因数
                for (int element : divisorList.get(0)) {
                    boolean flag = true;
                    for (int j = 1; j < divisorList.size(); j++) {
                        if (!divisorList.get(j).contains(element)) {
                            flag = false;
                            break;
                        }
                        divisorList.get(j).remove(divisorList.get(j).indexOf(element));
                    }
                    if (flag) {
                        result *= element;
                    }
                }

                return result;
            }
        }
    }


    public void run() {

        System.out.println(new Solution().minOperations(InputUtil.toIntegerArray("[40,38,18,19,18,18,16]"), InputUtil.toIntegerArray("[430222122,345833946,609158196,173124594,25468560,990277596,295095510,354571344,931500936,636837210]")));

        System.out.println(new Solution().minOperations(InputUtil.toIntegerArray("[2,3,2,4,3]"), InputUtil.toIntegerArray("[9,6,9,3,11]")));

        System.out.println(new Solution().minOperations(InputUtil.toIntegerArray("[14,14,8,14,14]"), InputUtil.toIntegerArray("[630016464,481269348,8818796]")));
        System.out.println(new Solution().minOperations(InputUtil.toIntegerArray("[3,2,6,2,35,5,35,2,5,8,7,3,4]"), InputUtil.toIntegerArray("[105,70,70,175,105,105,105]")));

        System.out.println(new Solution().minOperations(InputUtil.toIntegerArray("[2,3,2,4,3]"), InputUtil.toIntegerArray("[9,6,9,3,15]")));
        System.out.println(new Solution().minOperations(InputUtil.toIntegerArray("[4,3,6]"), InputUtil.toIntegerArray("[8,2,6,10]")));


//        int[] data1 = {26, 13};
//        int[] data2 = {735000, 421160, 238948};
//        int[] data3 = {1008, 1260, 882, 1134};
//
//        int result1 = new CommonMutiple().getCommonMutiple(data1);
//        int result2 = new CommonMutiple().getCommonMutiple(data2);
//        int result3 = new CommonMutiple().getCommonMutiple(data3);
//
//        System.out.println(result1);
//        System.out.println(result2);
//        System.out.println(result3);


    }

    public static void main(String[] args) throws Exception {
        LC6122 an = new LC6122();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
